#leetcode题目33：搜索旋转排序数组
#难度：中等
#时间复杂度：O(logn)
#空间复杂度：O(1)
#方法：二分查找

from typing import List
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid  

            elif nums[mid]<nums[right]: #右侧部分是升序的
                if target<=nums[right] and target>nums[mid]:
                    left=mid+1
                else:
                    right=mid-1
            else:
                if target>=nums[left] and target<nums[mid]:
                    right=mid-1
                else:
                    left=mid+1

        return -1

#测试数据
nums=[4,5,6,7,0,1,2]
target=0
#预期输出：4
solution=Solution()
print(solution.search(nums,target))

nums=[4,5,6,7,0,1,2]
target=3
#预期输出：-1
solution=Solution()
print(solution.search(nums,target))

nums=[1]
target=0
#预期输出：-1
solution=Solution()
print(solution.search(nums,target))

